/*
 * =====================================================================================
 *
 *       Filename:  Queue.h
 *
 *    Description:  Implement a queue with two stacks. Provide push, pop, size, empty 
 *                  member functions just as std::queue provided. Note that Queue is not
 *                  thread-safe
 *
 *        Version:  1.0
 *        Created:  04/23/2012 05:25:27 PM
 *       Revision:  none
 *       Compiler:  g++
 *
 *         Author:  shangmin.pku (Jesse Shang), shangmin.pku@gmail.com
 *
 * =====================================================================================
 */
#ifndef __QUEUE_H__
#define __QUEUE_H__

#include <stack>
#include <iostream>

namespace algorithm {
namespace practice {

using namespace std;

template<typename T>
class Queue {
private:
  void popAllFromStackAToStackB(stack<T>& stackA, stack<T>& stackB);
public:
  void push(const T& value);
  T& front();
  T& back();
  void pop();
  size_t size() const;
  bool empty() const;
private:
  stack<T> stack1_;
  stack<T> stack2_;
};

template<typename T>
void Queue<T>::push(const T& value) {
  stack1_.push(value);
}

template<typename T>
T& Queue<T>::front() {
  popAllFromStackAToStackB(stack1_, stack2_);
  T& element =  stack2_.top();
  popAllFromStackAToStackB(stack2_, stack1_);
  return element; 
}

template<typename T>
T& Queue<T>::back() {
  return stack1_.top();
}

template<typename T>
void Queue<T>::pop() {
  //if the Queue is empty, do nothing. Of course, you can throw an exception instead
  if (stack1_.empty()) {
    return;
  }
  popAllFromStackAToStackB(stack1_, stack2_);
  stack2_.pop();
  popAllFromStackAToStackB(stack2_, stack1_);
}

template<typename T>
size_t Queue<T>::size() const {
  return stack1_.size();
}

template<typename T>
bool Queue<T>::empty() const {
  return stack1_.empty();
}

template<typename T>
void Queue<T>::popAllFromStackAToStackB(stack<T>& stackA, stack<T>& stackB) {
  while (!stackA.empty()) {
    T topElementA = stackA.top();
    stackA.pop();
    stackB.push(topElementA);
  }
}

void init() {
  Queue<int> intQueue;
}

}
}

#endif
